<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>双向链表</title>
</head>
<body>
<script>
    function DoublelinkedList() {

        function Node(data) {
            this.data = data;
            this.next = null;
            this.pre = null;
        }

        //链表长度
        this.length = 0;
        //指向链表尾部节点
        this.tail = null;
        //指向链表头节点
        this.head = null;

        // 1.append方法
        DoublelinkedList.prototype.append = function (data) {
            // 1.根据data创建节点
            let newNode = new Node(data);

            // 2.判断添加的是否是第一个节点
            if(this.length === 0) {
                this.head = newNode;
            }else {
                newNode.pre = this.tail;
                this.tail.next = newNode;
            }
            this.tail = newNode;
            this.length += 1;
        };

        // 2.toString
        DoublelinkedList.prototype.toString = function () {
            let current = this.head;
            let resultString = "";
            while (current){
                resultString += current.data + " ";
                current = current.next;
            }
            return resultString;
        };

        // 3.insert
        DoublelinkedList.prototype.insert = function (position,data) {
            //1.越界判断
            if(position < 0 || position > this.length) {return false}
            //2.创建节点
            let newNode = new  Node(data);

            if(this.length === 0) { //无节点插入
                this.head = newNode;
                this.tail = newNode;
            }else {
                if(position === 0) { //有节点插入到第一个位置
                    this.head.pre = newNode;
                    newNode.next = this.head;
                    this.head = newNode;
                }else if(position === this.length) { //有节点插入到第最后一个位置
                    this.tail.next = newNode;
                    newNode.pre = this.tail;
                    this.tail = newNode;
                }else {  //插入到中部
                    let current = this.head;
                    let i = 0;
                    while (i++ < position) {
                        current = current.next;
                    }
                    //修改指向(插入操作)
                    newNode.next = current;
                    newNode.pre = current.pre;
                    current.pre.next = newNode;
                    current.pre = newNode;
                }
            }
            this.length += 1;
            return true;
        };

        // 4.get方法
        DoublelinkedList.prototype.get = function (index) {
            if(index < 0 || index >= this.length) {return false}
            // 判断get的元素靠近尾部还是更靠近头部
            if(this.length / 2 > index) { //靠近头部从头向尾遍历取
                let current = this.head;
                let i = 0;
                while (i++ < index) {
                    current = current.next;
                }
                return current.data;
            }else { //靠近尾部从尾向头遍历取
                let current = this.tail;
                let i = this.length - 1;
                while (i-- > index) {
                    current = current.pre;
                }
                return current.data;
            }
        };

        // 5.indexOf方法
        DoublelinkedList.prototype.indexOf = function (data) {
            let current = this.head;
            let index = 0;
            while (current) {
                if(current.data === data) {
                    return index;
                }
                index += 1;
                current = current.next;
            }
            return -1;
        };

        //6.update方法
        DoublelinkedList.prototype.update = function (index, newData) {
            if(index  < 0|| index >= this.length) {return false}
            if(this.length / 2 > index) {
                let current = this.head;
                let i = 0;
                while (i++ < index) {
                    current = current.next;
                }
                current.data = newData;
            }else {
                let current = this.tail;
                let i = this.length - 1;
                while (i-- > index) {
                    current = current.next;
                }
                current.data = newData;
            }
            return true;
        };

        //7.removeAt
        DoublelinkedList.prototype.removeAt = function (index) {
            if (index < 0 || index >= this.length) {return false}

            if(this.length === 1) { //链表只有一个节点时
                this.head = null;
                this.tail = null;
            }else {
                if (index === 0) {  //移除第一个节点
                    this.head = this.head.next;
                    this.head.pre = null;
                }else if(index === this.length - 1) {
                    this.tail = this.tail.pre;
                    this.tail.next = null;
                }else {
                    if(this.length / 2 > index) {
                        let i = 0;
                        let current = this.head;
                        while (i++ < index) {
                            current = current.next;
                        }
                        current.next.pre = current.pre;
                        current.pre.next = current.next;
                    }else {
                        let i = this.length - 1;
                        let current = this.tail;
                        while (i-- > index) {
                            current = current.pre;
                        }
                        current.next.pre = current.pre;
                        current.pre.next = current.next;
                    }

                }
            }
            this.length -= 1;
            return true;
        };

        //8.remove方法
        DoublelinkedList.prototype.remove = function (element) {
            if(this.length === 1 && this.head.data === element) {
                this.head = null;
                this.pre = null;
                return 0;
            }else {
                let index = false;
                if(this.head.data === element) {
                    this.head = this.head.next;
                    this.head.pre = null;
                    index = 0;
                }else if(this.tail.data === element)  {
                    this.tail = this.tail.pre;
                    this.tail.next = null;
                    index = this.length - 1;
                }else {
                    let current = this.head.next;
                    index = 1;
                    while (current) {
                        if(current.data === element) {
                            break;
                        }
                        current = current.next;
                        index += 1;
                    }
                    current.next.pre = current.pre;
                    current.pre.next = current.next;
                }
                if(index) {
                    this.length -= 1;
                }
                return index;
            }
        };

        // 9.isEmpty方法
        DoublelinkedList.prototype.isEmpty = function () {
            return this.length === 0;
        };

        // 10.size方法
        DoublelinkedList.prototype.size = function () {
            return this.length;
        };

        DoublelinkedList.prototype.getHead = function () {
            return this.head.data;
        };

        DoublelinkedList.prototype.getTail = function () {
            return this.tail.data;
        };



    }
    let list = new DoublelinkedList();

    list.append("艾伦");
    list.append("泰勒");
    list.append("三笠");
    list.append("JOJO");
    list.insert(1, "鲁鲁修");
    console.log(list.toString());
    console.log(list.get(3));
    console.log(list.indexOf("三笠"));
    list.update(1, "CC");
    console.log(list.toString());
    list.removeAt(4);
    console.log(list.toString());
    list.remove("泰勒");
    console.log(list.toString());
    console.log(list.length);
</script>
</body>
</html>